#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>
#include <unordered_map>
#include <queue>

using namespace std;

// 首先来一个Trie树节点定义
struct TrieNode {
   //由字典树知道，我们需要标记是否为单词结尾
    bool isEnd; 
	// 然后如果是的话，就在这里记录单词出现的次数
    int count;        
    TrieNode* children[26]; // 子节点指针数组，对应26个字母,其内容是当前节点的子节点是这个字母的子节点编号

    //为了方便初始化节点
    TrieNode() : isEnd(false), count(0) {
        for (int i = 0; i < 26; ++i) {
            children[i] =NULL; // 初始化所有子节点为空
        }
    }
};

//接下来写一下往这颗字典树里里面插入单词的函数
void insert(TrieNode*root,string&word){
	TrieNode*node=root;
	for(char ch : word){
		int index=ch-'a';//把对应的英文换成数字编码，从而和设置字典树的节点的26个子节点对应上
		if(!node->children[index]){
			//当我们需要储存的下一个节点是当前这个字母的找不到的时候
			//创建新的节点
			node->children[index]=new TrieNode();
		}
		node=node->children[index];//移动到子节点
	}
	//然后一个单词就放完了，我们现在标记一下单词结尾
	node->isEnd=true;//代表结尾
	node->count++;//增加单词出现次数
}

//为了排序，收集树里面的单词及个数
void collectWord(TrieNode*node,string currentWord,vector<pair<string,int>>&words){
	if(node->isEnd){
		//如果是单词结尾，那么可以返回它到我们需要的这个符合数据类型里面
		words.push_back({currentWord,node->count});
	}
	for(int i=0;i<26;++i){
		if(node->children[i]){
			collectWord(node->children[i],currentWord+char('a'+i),words);
			//递归，得出每一个单词及其次数
		}
	}
}

int main() {
    ifstream file("in.txt"); // 打开文件in.txt
    if (!file.is_open()) {
        cerr << "打开失败，请检查错误" << endl; // 如果文件打开失败，输出错误信息
        return 1;
    }

    TrieNode* root = new TrieNode(); // 创建Trie树的根节点
    string line;
    while (getline(file, line)) { // 逐行读取文件内容
        string word;
        for (char ch : line) {
            if (isalpha(ch)) {
                word += tolower(ch); // 因为没遇到空格，还是一个单词，将字母转换为小写并拼接成单词
            } else if (!word.empty()) {
            	//说明遇到空格了，需要把前面弄好的单词存起来来了
                insert(root, word); // 插入单词到Trie树
                word.clear(); // 清空当前单词，方便存下一个单词
            }
        }
        //想一下可以知道还会剩下一个单词
        if (!word.empty()) {
            insert(root, word); // 插入最后一个单词
        }
    }
    file.close(); // 关闭文件
    
    //创建一个复合数据类型，结合了 vector 容器和 pair 结构体
    vector<pair<string,int>>words;//储存所有的单词及其出现次数，方便排序
    //收集这个树里面所有单词
    collectWord(root,"",words);
    
    //因为这是自己定义的数据类型，要自己定义如何比较
    sort(words.begin(),words.end(),[](const pair<string,int>&a,const pair<string,int>&b){
    	return a.second>b.second||(a.second == b.second && a.first < b.first);
	});
      // 输出前100个单词及其出现次数
      //因为题目给的都没有100个数据，所以我们要取最小
       int limit = min(100, static_cast<int>(words.size()));
    for (int i = 0; i <limit; ++i) {
        cout << words[i].first << " " << words[i].second << endl;
    }

    return 0;
    
    
}